package lanQiaoBei.数学知识.同余方程;

import java.util.Scanner;

/*(扩展欧几里得算法求同余方程)
 求关于 x
 的同余方程 ax≡1(modb)
 的最小正整数解。

输入格式
输入只有一行，包含两个正整数 a,b
，用一个空格隔开。

输出格式
输出只有一行，包含一个正整数 x
，表示最小正整数解。

输入数据保证一定有解。

数据范围
2≤a,b≤2×109
输入样例：
3 10
输出样例：
7
 */
public class P1 {
       static Scanner sc=new Scanner(System.in);
       static int x,y;
       static int egcd(int a,int b){
    	      if(b==0){
    	    	  x=1;y=0;
    	    	  return a;
    	      }
    	      int d=egcd(b, a%b);
    	      int t=x;
    	      x=y;
    	      y=t-a/b*y;//这里必须先算a整除b
    	      return d;
       }
       public static void main(String[] args) {
		      int a=sc.nextInt(),b=sc.nextInt();
		      System.out.println(egcd(a, b));
		      System.out.println((x%b+b)%b);
		      System.out.print((y%b+b)%b);
	}
}
